<!DOCTYPE html PUBLIC "-//w3c//dtd html 4.0 transitional//en">
<html>
<head>
  <meta http-equiv="Content-Type"
 content="text/html; charset=iso-8859-1">
  <meta name="GENERATOR"
 content="Mozilla/4.7 [en]C-CCK-MCD NSCPCD47  (Win95; I) [Netscape]">
</head>
<body>
<h1>
JET HMM Tools</h1>
JET provides the basic tools for building Hidden Markov Models (HMMs),
and for using HMMs to annotate text.&nbsp; Two simple annotators are
included
in JET, a part-of-speech tagger and a name tagger;&nbsp; this
documentation
is provided to allow users to modify these taggers and to write their
own
taggers.
<p>There are four separate components:
</p>
<ul>
  <li>
    <a href="#HMM">the HMM</a></li>
  <li>
    <a href="#HMMannotator">the HMMannotator</a>, which uses an HMM to
annotate
documents</li>
  <li>
the part-of-speech tagger</li>
  <li>
the name tagger</li>
</ul>
The HMM and HMMannotator are described below in separate sections.
<h2><a name="HMM"></a>The HMM</h2>
JET provides a set of classes for defining HMMs.&nbsp; The principal
classes
are
<ul>
  <li>
    <tt>HMM</tt></li>
  <li>
    <tt>HMMstate</tt></li>
  <li>
    <tt>HMMarc</tt></li>
  <li>
    <tt>HMMemitter</tt></li>
</ul>
The HMM is made up of a set of <tt>HMMstate</tt>s.&nbsp; Each <tt>HMMstate</tt>
in turn has an <tt>HMMemitter</tt>, which specifies which tokens can
be
emitted by that state, and a set of <tt>HMMarc</tt>s, which indicate
which
states can follow the current state, and with what probability.&nbsp;
Note
that in JET HMMs, emission is associated with states, not arcs.&nbsp;
Every
state emits exactly one token.
<p><tt>HMMemitter</tt> is an abstract class.&nbsp; The actual emitter
class
used in a specific HMM must be an extension of HMMemitter.&nbsp; Two
such
extensions are currently implemented, <tt>BasicHMMemitter</tt> and <tt>WordFeatureHMMemitter</tt>.
</p>
<p>Every state has a name.&nbsp; Every HMM should have a state named "<tt>start</tt>"
and a state named "<tt>end</tt>".&nbsp; The HMM always begins in the <tt>start</tt>
state, and always ends in the <tt>end</tt> state.&nbsp; The <tt>start</tt>
and <tt>end</tt> states do not emit tokens;&nbsp; therefore, a
sequence
of <i>n</i>+2 states, including the <tt>start</tt> and <tt>end</tt>
states,
generates a sequence of <i>n</i> tokens.
</p>
<h3>External Representation of an HMM</h3>
An HMM has an external (readable) representation.&nbsp; This
representation
is generated by method <tt>HMM.store</tt>, and can be read by <tt>HMM.load</tt>.&nbsp;
This representation consists of a series of lines each beginning with a
keyword.&nbsp; The following types of lines are generated and
recognized:
<dl>
  <dt><b><tt>STATE</tt></b> <i>state-name</i></dt>
  <dd>Defines a new state with name <i>state-name</i>.&nbsp; All
following lines
until the next STATE line are part of the definition of this state.</dd>
  <dt><b><tt>ARC TO</tt></b> <i>state-name</i> [<i>count</i>]</dt>
  <dd>Indicates that there is an arc from the current state to the
state named
    <i>state-name</i>.&nbsp;
The <i>count</i>, which will be used to compute the probability of
this
transition, indicates how often the transition to <i>state-name</i>
was
observed.&nbsp; If absent, a count of 1 is assumed.</dd>
  <dt><b><tt>EMIT</tt></b> <i>token</i> [<i>count</i>]</dt>
  <dd>Indicates that the current state can emit token token.&nbsp; The <i>count</i>,
which will be used to compute the probability of this emission,
indicates
how often the emission of <i>token</i> was observed.&nbsp; If absent,
a
count of 1 is assumed.</dd>
  <dt><b><tt>TAG</tt></b> <i>tag</i></dt>
  <dd>Indicates that the current state is associated with tag <i>tag</i>.&nbsp;
These tags are used to associate HMM states with annotations, as
explained
below.</dd>
</dl>
Keywords (STATE, ARC, TO, EMIT, TAG) may be in upper or lower
case.&nbsp;
Blank lines are allowed in the file.
<p>An example of a simple file which matches a sequence of "oink"s and
"quacks" is:
</p>
<blockquote><tt>STATE start</tt>
  <br>
  <tt>ARC TO middle</tt>
  <br>
  <tt>STATE middle</tt>
  <br>
  <tt>EMIT quack 1</tt>
  <br>
  <tt>EMIT oink 2</tt>
  <br>
  <tt>ARC TO middle 2</tt>
  <br>
  <tt>ARC TO end 1</tt>
  <br>
  <tt>STATE end</tt></blockquote>
<h3>
Defining the HMM Topology</h3>
The first step in creating an HMM is to define its topology --- its
states
and arcs (i.e., to define its possible transitions, but not the
transition
or emission probabilities).&nbsp; The topology can be defined in two
ways.&nbsp;
First, you can describe it in the external representation (omitting the
counts),
<br>
and then create an HMM with
<dl>
  <dl>
    <tt>HMM h = new HMM();</tt><br>
    <tt>h.load(new BufferedReader (new FileReader (<i>file-name</i>)));</tt>
  </dl>
</dl>
Alternatively, you can create the HMM with calls to the <tt>HMMstate</tt>
and <tt>HMMarc</tt> constructors:
<blockquote><tt>HMM h = new HMM();</tt>
  <br>
  <tt>HMMstate start = new HMMstate("start", "", BasicHMMemitter.class);</tt>
  <br>
  <tt>start.addArc( new HMMarc("middle", 0));</tt>
  <br>
  <tt>h.addState(start);</tt>
  <br>
  <tt>HMMstate middle = new HMMstate("middle", "personTag",
BasicHMMemitter.class);</tt>
  <br>
  <tt>middle.addArc(new HMMarc("middle",0));</tt>
  <br>
  <tt>middle.addArc(new HMMarc("end", 0));</tt>
  <br>
  <tt>h.addState(middle);</tt>
  <br>
  <tt>HMMstate end = new HMMstate("end", "", BasicHMMemitter.class);</tt>
  <br>
  <tt>h.addState(end);</tt>
  <br>
  <tt>h.resolveNames();</tt></blockquote>
The latter approach is particularly useful for large, regular HMMs,
such
as ergodic HMMs.
<h2><a name="HMMannotator"></a>The HMMannotator:&nbsp; associating HMMs
with
annotations</h2>
<h3>
Defining the correspondence</h3>
Most processing in JET works by adding annotations to a document.&nbsp;
In the case of HMMs, we do this by associating particular states of the
HMM with particular annotations on the document.&nbsp; This is done by
class <tt>HMMannotator</tt>.&nbsp; The properties of an <tt>HMMannotator</tt>
determine the correspondence between the HMM and the annotations.
<p>One of the properties of an <tt>HMMstate</tt> is its <i>tag</i>.&nbsp;
The tag is used to establish the correspondence between the HMM state
and
the annotations;&nbsp; all states with the same tag are considered
equivalent
for annotation purposes.&nbsp; (In simple cases, we will set the tag of
a state equal to its name, but having names and tags separate allows
for
greater flexibility.)
</p>
<p>The most important property of an <tt>HMMannotator</tt> is its <b>tagTable</b>.&nbsp;
The tag table is of type <tt>String[][4]</tt>.&nbsp; Each row of the
tag
table is a quadruple:
</p>
<blockquote>{annotation-type,&nbsp;&nbsp;&nbsp;
annotation-attribute,&nbsp;&nbsp;&nbsp;
annotation-value,&nbsp;&nbsp;&nbsp; tag}</blockquote>
This row says that tag <i>tag</i> corresponds to having an annotation
of
type <i>annotation-type</i> with attribute <i>annotation-attribute</i>
with value <i>annotation-value.</i>&nbsp;&nbsp; For example,
<blockquote><tt>{"namex",&nbsp;&nbsp;&nbsp; "type",&nbsp;&nbsp;&nbsp;
"person",&nbsp;&nbsp;&nbsp;
"personTag"}</tt></blockquote>
indicates that the state with tag <tt>personTag</tt> corresponds to an
annotation on the document of <tt>&lt;namex type=person&gt; ...
&lt;/namex&gt;</tt>.&nbsp;
This means that, if we analyze a document with an HMM, and in the most
likely analysis the word "Anastasia" is matched by state "middle" which
has tag "middleTag", then we will add an annotation <tt>&lt;namex
type=person&gt;Anastasia&lt;/namex&gt;.</tt>&nbsp; The tag table can be
read from a file, one row per line, by the <span
 style="font-family: monospace;">readTagTable </span>method.<tt><br>
</tt>
<p>This doesn't completely define the correspondence, however.&nbsp;
Suppose
the document contains the words "Albert Anastasia", and both tokens
"Albert"
and "Anastasia" are matched by the same state, with tag
middleTag.&nbsp;
Should we generate one namex annotation covering both words, or two
separate
annotations?&nbsp; If the property <b>annotateEachToken</b> is true,
then
a separate annotation is produced for each token;&nbsp; this is
appropriate,
for example, for part-of-speech tagging, where each token should be
separately
tagged.&nbsp; If this property is false, then a single annotation is
generated
for one or more consecutive states with the same tag;&nbsp; this is
appropriate
whenever we need to tag multi-token items.
</p>
<p>This is not quite sufficient, because we may have two consecutive
multi-word
names, as in the sentence "By accident, I called Albert Anastasia Fred
Smith.", which we would like to annotate as "By accident, I called
&lt;namex
type=person&gt;Albert Anastasia&lt;/namex&gt; &lt;namex
type=person&gt;Fred Smith&lt;/namex&gt;."&nbsp;
To handle such cases, we must distinguish the state which start a
person
name from the state which continues a person name.&nbsp; This is done
with
the <b>BItag</b> property.&nbsp; If BItag is false, correspondences
are
as previously described.&nbsp; If BItag is true, and the tag table is
as
given above, then the state corresponding to the first token of a name
must have tag <tt>B-personTag</tt>, while the state corresponding to
the
continuation of a name must have tag <tt>I-personTag</tt>.
</p>
<p>To build an annotator based on an HMM, we first create the HMM (as
described
in the previous section),
</p>
<blockquote><tt>HMM h = new HMM();</tt></blockquote>
then create an annotator using this HMM,
<blockquote><tt>HMMannotator annotator = new HMMannotator (h);</tt></blockquote>
and finally set the properties of this annotator, using<br>
<blockquote><tt>annnotator.setTagTable (...)<br>
  </tt></blockquote>
or<br>
<blockquote><tt>annotator.readTagTable (...)<br>
  </tt></blockquote>
<h3>
Training the HMMannotator</h3>
Once a correspondence has been established, we can use the HMMannotator
to train the HMM.&nbsp; If we have a collection of documents with the
appropriate
annotations, this can be done by the <tt>HMMannotator.train</tt>
method:
<blockquote><tt>Jet.Tipster.Collection col = new
Jet.Tipster.Collection(...);</tt>
  <br>
  <tt>annotator.train (col);</tt>
  <br>
  <tt>h.computeProbabilities();</tt></blockquote>
HMMannotator.train applies the HMM separately to each sentence
(sequence
of tokens marked with an <b>S</b> annotation) in the document.&nbsp;
This
can be changed by using the <b>zoneToTag</b> property of the
annotator.
<h3>Using the trained HMMannotator</h3>
The trained annotator can then be used to annotate new documents.&nbsp;
The <tt>HMMannotate.annotate</tt> method annotates each sentence in
the
document (again, the unit to annotate can be changed through the
zoneToTag
property).
<br>
&nbsp;
</body>
</html>
